/**
 * 堆排序
 * 左子结点或右子结点的值均比父结点大或者小称为大根堆小根堆
 *  当前结点下标为i，则其父结点下标为(i-1)/2
 *  当前结点下标为i，则其左子结点下标为2*i+1,右子结点下标为2*i+2
 */
public class HeapSort {
    int len = 0;

    /**
     * 交换nums下标i和j的值
     * @param nums
     * @param i
     * @param j
     */
    private void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /**
     * 对nums构建堆
     * 本类构建大根堆
     * @param nums
     */
    private void buildHeap(int[] nums){
        for (int i = len/2-1; i >= 0; i--) {
            adjustHeap(nums,i);
        }
    }

    /**
     * 维护nums下标i到len的堆
     * @param nums
     * @param i
     */
    private void adjustHeap(int[] nums,int i){
        int maxIndex = i;
        int l_index = 2*i+1; //左子结点下标
        int r_index = 2*i+2; //右子节点下标
        if(l_index<len&&nums[l_index]>nums[maxIndex]) //存在左子结点且比父结点值大
            maxIndex = l_index;
        if(r_index<len&&nums[r_index]>nums[l_index]&&nums[r_index]>nums[i]) //存在右子结点且比左兄弟值大且比父结点值大
            maxIndex = r_index;
        if(maxIndex!=i){
            swap(nums,i,maxIndex);  //交换父节点值和子结点值
            adjustHeap(nums,maxIndex); //递归调整 maxIndex
        }

    }

    /**
     * 堆排序
     * @param nums
     */
    public void sort(int[] nums){
        len = nums.length;
        if(len<1) return ;
        //构建一个最大堆
        buildHeap(nums);
        /**
         * 在一个堆结构中，拿堆顶和最后一个交换，最后一个即当前循环迭代最大值
         */
        while (len>0){
            swap(nums,0,len-1); //nums 堆最后一个为当前循环最大值
            len--; //adjustHeap会调整nums[0]~nums[len-1]
            adjustHeap(nums,0);
        }
    }

    public static void main(String[] args) {
        int[] nums = {3,9,-1,7,5,10,21,33};
        HeapSort heapSort = new HeapSort();
        heapSort.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]+" ");
        }
    }

}
